package Tree._173_BinarySearchTreeIterator;

import java.util.ArrayList;
import java.util.List;

public class BSTIterator {
    List<Integer> res = new ArrayList<>();
    int pos = 0;
    int length;
    public BSTIterator(TreeNode root) {
        preOrderTraversal(root);
        length = res.size();
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if (pos < length) {
            return true;
        } else {
            return false;
        }
    }

    /** @return the next smallest number */
    public int next() {
        return res.get(pos++);
    }

    public void preOrderTraversal(TreeNode root) {
        if (root != null) {
            preOrderTraversal(root.left);
            res.add(root.val);
            preOrderTraversal(root.right);
        }
    }
}
